


#include <iostream>
#include <string>
#include <vector>
using namespace std;

void Test1()
{
    string s;
    int cnt[26] = { 0 };

    while (getline(cin, s))
    {
        for (const auto& e : s)
        {
            if (!isblank(e))
                ++cnt[e - 'a'];
        }
    }

#if 0
    while (true)
    {
        getline(cin, s);
        if (s.empty())
            break;
        for (const auto& e : s)
        {
            if (!isblank(e))
                ++cnt[e - 'a'];
        }
    }
#endif

    char res = 'a';
    for (int i = 1, maxcnt = cnt[0]; i < 26; ++i)
    {
        if (cnt[i] > maxcnt)
        {
            maxcnt = cnt[i];
            res = i + 'a';
        }
    }

    cout << res << endl;
}


bool Is(int n)
{
    if (1 == n)
        return true;

    for (int i = 1; i <= n / 2; ++i)
    {
        if (i * i == n)
            return true;
    }

    return false;
}

void Test2()
{
    int n = 0;
    cin >> n;

    int res = 1;
    vector<int> v;

    if (Is(n))
    {
        cout << res << endl;
        return;
    }

    for (int i = 1; i < n; ++i)
    {
        if (Is(i))
            v.push_back(i);
    }

    res = 0;
    int sum = 0;
    for (int i = v.size() - 1; true;)
    {
        ++res;

        if (sum + v[i] < n)
        {
            sum += v[i];
        }
        else if (sum + v[i] > n)
        {
            while (i >= 0 && sum + v[i] > n)
            {
                --i;
            }
            if (sum + v[i] == n)
                break;

            sum += v[i];
        }
        else
        {
            break;
        }
    }

    cout << res << endl;
}

int main()
{
    // Test1();
    Test2();

    return 0;
}